package com.xyhuo.leetcode.january;

/**
 * 加油站
 * https://leetcode.cn/problems/gas-station/
 *
 * @time 2024/1/17
 */
public class CanCompleteCircuit {

//    public static void main(String[] args) {
//        CanCompleteCircuit ccc = new CanCompleteCircuit();
//        int[] gas = {5, 1, 2, 3, 4};
//        int[] cost = {4, 4, 1, 5, 1};
//        ccc.canCompleteCircuit(gas, cost);
//    }

    public int canCompleteCircuit(int[] gas, int[] cost) {

        boolean eq = true;
        for (int i = 0; i < gas.length; i++) {
            if (gas[i] != cost[i]) {
                eq = false;
                break;
            }
        }
        if (eq) {
            return 0;
        }

        for (int i = 0; i < gas.length; i++) {
            if (gas[i] == cost[i]) {
                continue;
            }
            boolean search = search(i, gas, cost);
            if (search) {
                return i;
            }
        }
        return -1;
    }

    private boolean search(int startIndex, int[] gas, int[] cost) {
        int all = 0;
        for (int i = 0; i < gas.length; i++) {
            int index = startIndex + i < gas.length ? startIndex + i : startIndex + i - gas.length;
            if (all + gas[index] >= cost[index]) {
                all = all + gas[index] - cost[index];
            } else {
                return false;
            }
        }
        return true;
    }
}
